package 动态规划;

public class LeetCode343_整数拆分 {
    // 可以用数学归纳法证明对任意一个整数最大的拆分形式为 n = 2^p * 3^q (n >= 3, p, q为自然数)，
    // 并且q应该尽可能大（理由：如果q减少2，则p要增加3，而2^3 < 3^2，因此应该尽可能增加q）
    /*
    n -> memo(n)
    将n 分成两个数字    memo(n) = i * (n - i);
    将n 分成多个数字
        memo(n) = memo(i) * (n - i);
        memo(n) = i * memo(n - i);
        memo(n) = memo(i) * memo(n - i);

    memo(n) = Math.max(a,b,c,d);
*/
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            int curMax = 0;
            for (int j = 1; j < i; j++) {
                curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));
            }
            dp[i] = curMax;
        }
        return dp[n];
    }


}
